package com.gwcloud.leetcode.tags.tree;

import com.gwcloud.leetcode.common.datastructure.TreeNode;

/** 
* @ClassName   : Leetcode106 
* @author      : ganwei 
* @date        : 2020年5月5日 
* @Description : 106. 从中序与后序遍历序列构造二叉树 
*/
public class Leetcode0106 {
	/**
	 * -解题思路,后序遍历顺序为左右根
	 */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    	if(inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0 || inorder.length != postorder.length) {
    		return null;	
    	}
    	return build(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    
    public TreeNode build(int[] inorder,int iStart,int iEnd,int[] postorder,int pStart,int pEnd) {
    	if(iStart > iEnd || pStart >pEnd) {
    		return null;
    	}
    	TreeNode node = new TreeNode(postorder[pEnd]);
    	int index = 0;
    	while(inorder[iStart+index] != postorder[pEnd]) {
    		index++;
    	}
    	
    	//构建左子树
    	node.left = build(inorder,iStart,iStart+index-1,postorder,pStart,pStart+index-1);
    	//构建右子树
    	node.right = build(inorder,iStart+index+1,iEnd,postorder,pStart+index,pEnd-1);
    	
    	return null;
    }
	public static void main(String[] args) {
		Leetcode0106 l106 = new Leetcode0106();
		int[] inorder  = {9,3,15,20,7};
		int[] postorder = {9,15,7,20,3};
		l106.buildTree(inorder, postorder);
	}
}
